js链表操作

2023-08-15 21:59| 来源: 网络整理| 查看: 265

在这里插入图片描述 next指向下一个节点的地址链表中的节点:每一个节点通常最少有两个属性，一个表示该节点的值，可以用val来表示，另外一个就是指向下一个节点的指针，可以用next表示。

function ListNode(val) { this.val = val; this.next = null; }

第一题

思路：不给单链表，给的是单链表中要删除的节点node，这个node已经存在单链表中，即这个节点的前一个节点是未知的，但下一个节点是可以知道的，那么可以把下一个的值赋给这个node，然后删除下一个节点即可：即把node下一个节点的地址

var deleteNode = function(node) { node.val = node.next.val; node.next = node.next.next; }; //创建节点 function ListNode(val) { this.val = val; this.next = null; } var node1=new ListNode(1); var node2=new ListNode(2); var node3=new ListNode(3); var node4=new ListNode(4); var node5=new ListNode(5); node1.next=node2; node2.next=node3; node3.next=node4; node4.next=node5; deleteNode(node2); console.log(node1);//删掉了node2节点 console.log(node2); console.log(node3);

打印结果：第二题思路：这道题要用双指针来实现。先用first指针前进n，然后让second从head开始和first一起前进，直到first到了末尾，此时second的下一个节点就是要删除的节点。（另外，若first一开始前进n就已经不在链表中了，说明要删除的节点正是head节点，那么直接返回head的下一个节点接口。）

删除了头节点第三题在这里插入图片描述思路：递归：先找到最后一个节点，每次将头节点插到最后

var reverseList = function(head) { if (head == null || head.next == null) return head; var list = reverseList(head.next); var last = list; while (last.next != null) last = last.next; last.next = head; head.next = null; return list; };

第四题在这里插入图片描述思路：递归解决：若其中某条链表为空，那必然是返回另一条不为空的了。比较两条链表的头节点的大小，将较小者作为新链表的头节点，然后递归调用方法即可。

var mergeTwoLists = function(l1, l2) { if(!l1) return l2; if(!l2) return l1; let head; if (l1.val head=l2; head.next=mergeTwoLists(l1,l2.next); } return head; };

第四题思路：O(n)的时间复杂度意味着只能遍历一趟链表，O(1)的空间复杂度意味着只能使用常数个变量（也就是不能使用数组、集合等变量）。于是想到，设置两个字符串变量，一个保存正向的链表元素，一个保存反向的链表元素，遍历完判断是否相等即可。

var isPalindrome = function(head) { let str = '', // 正向 str_reverse = '' // 反向 while (head) { str += head.val; str_reverse = head.val + str_reverse;//将下一个放在前面 head = head.next; } return str === str_reverse; };

第五题思路：设置两个指针p1，p2。p1每次走一步，p2每次走两步。若没有环，则两者不会碰到，若有环，则必然会碰到。

var hasCycle = function(head) { if(!head||!head.next) return false; let p1=head,p2=head.next; while(p2&&p2.next){ if(p1==p2) return true; p1=p1.next; p2=p2.next.next; } return false; };

三个反转，最后不足三个的不反转,如12345 ，反转成32145

//思路：进行三个拆分，然后每个进行反转 //引用类型:存储在堆中，所有的变量在内存中是同一块地址 var reverseList = function(head) { if (head == null || head.next == null) return head; var list = reverseList(head.next); var last = list; while (last.next != null) last = last.next; last.next = head; head.next = null; return list; }; function ListNode(val) { this.val = val; this.next = null; } var reverseListN = function(head, n){ debugger var end = head; var next = head; for (var i = 0; i return head; } end = end.next; } next = end.next; end.next = null; reverseList(head); head.next = reverseListN(next, n);// head.next是4，5 return end; } var node1=new ListNode(1); var node2=new ListNode(2); var node3=new ListNode(3); var node4=new ListNode(4); var node5=new ListNode(5); node1.next=node2; node2.next=node3; node3.next=node4; node4.next=node5; console.log(reverseListN(node1, 3))

【本文地址】

公司简介

联系我们